Hyem.log

[프로그래머스] 소수찾기 (파이썬)

August 02, 2021

문제

문제 설명

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.

각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

제한사항

numbers는 길이 1 이상 7 이하인 문자열입니다. numbers는 0~9까지 숫자만으로 이루어져 있습니다. “013”은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.

입출력 예

numbers return
“17” 3
“011” 2

입출력 예 설명

예제 #1
[1, 7]으로는 소수 [7, 17, 71]를 만들 수 있습니다.

예제 #2
[0, 1, 1]으로는 소수 [11, 101]를 만들 수 있습니다.
11과 011은 같은 숫자로 취급합니다.


풀이 과정

소수인지 찾는건 둘째치고… 일단 주어진 숫자로 몇 가지의 서로다른 숫자를 만들어낼 수 있는지부터 구해야한다. 이를 위해 순열을 구하면 되는데… 이게 정말 힘들었다ㅠ 일단 파이썬에 쉽게 순열/조합을 구할 수 있는 모듈이 있어서 사용해보았다.


(1) itertools 모듈로 순열 구하기

💡 파이썬 itertools 모듈

  • product(p,q, …, [repeat=n]) : 데카르트 곱
  • permutations(p, r) : p 중에서 r개를 뽑는 순열
  • combinations(p, r) : p중에서 r개를 뽑는 조합
  • combinationswithreplacement(p, r) : p중에서 r개를 뽑는 중복조합
    파이썬 API 문서 참고

주의할 점은, 이 함수들은 generator이다. 즉 루프를 돌며 한번 값을 던져주고 나면 그 값이 기억되지 않는다. 그렇기 때문에 이런 함수들을 쓰고 나서는 list() 등을 통해 iterator 객체에 값을 담아놔야 한다.

이 문제에서는 numbers에 같은 숫자가 들어있는 경우 중복 결과값이 나올 수도 있으니 set에 넣어서 중복을 제거해주면 되겠다. (itertools 모듈과 generator 개념에 대해서는 나중에 다시 자세하게 포스팅해야겠다)

만들 수 있는 모든 숫자들을 구했으면, 이제 이것들이 소수인지 아닌지 판별한다. 💎 n이 소수인지 판별할때는 1과 자신 외에 약수가 있는지 확인해보면 되는데, 약수를 구할때는 n의 제곱근까지만 확인해보면 된다!!


완성 코드

from itertools import permutations
import math

def solution(numbers): 
    result = set()
    for r in range(1, len(numbers)+1):
        for p in permutations(numbers, r):
            result.add(int(''.join(p)))
            # permutations는 generator 이기 때문에 루프 한번 돌고 결과값 사라짐
            # set에 담기
                            
    answer = 0
    for num in result:
        check = 0
        if num < 2:
            check = 1  # 1이면 소수 아님
        elif num == 2:
            pass   # 2이면 소수임
        else:     
            for i in range(2, int(math.sqrt(num))+1):            
                if num % i == 0:                
                    check = 1
                    break        
        if check == 0:            
            answer += 1

    return answer

(2) 재귀함수로 순열 구하기

모듈을 사용하지 않고 순열을 구하기 위해 재귀함수를 사용하였다.

def permutation(numbers):
    used = [0]*len(numbers) # 숫자 만들때 해당 숫자를 뽑았는지 안뽑았는지 표시하는 용도의 리스트(중복 선택 막기위해)
    result = set() # numbers에 중복된 숫자 있는 경우 - set으로 정답 중복 제거
    
    for r in range(1, len(numbers)+1):

        # numbers 중 r개의 숫자 뽑은 모든 결과 구하는 함수
        def generate(value, used):
            # 재귀함수 종료조건: 만든 숫자의 길이가 r이 되면 종료
            if len(value) == r:
                result.add(int(value)) # int 변환 - 맨 앞자리 0 제거
                return            
            # 재귀함수 본문
            for i in range(len(numbers)):
                if used[i] == 0: 
                    value += numbers[i] # 숫자를 뽑아서 길이가 r이 될때까지 더해나간다
                    used[i] = 1 # 숫자 뽑을때 중복방지
                    generate(value, used) 
                    
                    # 재귀함수 종료후, 직전 상태로 되돌아가서 for문 마저 실행
                    value = value[:-1]
                    used[i] = 0

        # 모든 r에 대해 generate 함수 수행
        generate("", used)
    return result

완성 코드

import math

# 최종 함수
def solution(numbers):
    result = permutation(numbers)
    return prime_number(result)

# 순열 구하는 함수
def permutation(numbers):
    used = [0]*len(numbers) 
    result = set() 

    for r in range(1, len(numbers)+1):
        def generate(value, used):
            if len(value) == r:
                result.add(int(value)) 
                return            
            
            for i in range(len(numbers)):
                if used[i] == 0: 
                    value += numbers[i] 
                    used[i] = 1 
                    generate(value, used)
                    value = value[:-1]
                    used[i] = 0
        
        generate("", used)
    
    return result


# 소수 몇개인지 반환하는 함수
def prime_number(numbers):
    answer = 0
    for num in numbers:
        check = 0
        if num < 2:
            check = 1
        elif num == 2:
            pass
        else:     
            for i in range(2, int(math.sqrt(num))+1):            
                if num % i == 0:                
                    check = 1
                    break        
        if check == 0:            
            answer += 1   
    return answer
Written by@[hyem]
Hyem's Dev Note

GitHub